Field of the Invention
The invention relates in general to an image processing circuit and a method thereof, and more particularly to a circuit that calculates a weighted sum of absolute difference (WSAD) of an image and a method thereof.
Description of the Related Art
FIG. 1 shows a schematic diagram of a conventional similarity matching procedure based on a window. A target image 110 includes a target window 115. In the matching procedure, a search window 123 is first determined from a reference window 120, and a plurality of matching candidates (or referred to as matching windows) 125 are identified from the search window 123. A sum of absolute difference (SAD) operation is then performed on the matching windows 125 and the target window 115. To determine the search window 123, a corresponding point 127 corresponding to a center 117 of the target window 115 may be first identified from the reference window 120 (i.e., the center 117 and the corresponding point 127 have the same coordinates in the target image 110 and the reference image 120), so as to determine a position of the search window 123 and then determine a size of the search window 123 according to a range to be matched. After having determined the search window 123, a plurality of matching windows 125 may then be identified therefrom. For example, a corresponding relationship of the matching window 125 and the corresponding point 127 is as shown by matching windows 125-00 to 125-nk below the reference image 120 in FIG. 1. As shown, each of the matching windows 125 has a width of n+1 pixels and a height of k+1 pixels, and includes the corresponding point 127, where n and k are both positive integers. Further, the search window 123 has a width of 2n+1 pixels and a height of 2k+1 pixels. FIG. 2 shows a schematic diagram of a corresponding relationship of the matching window 125, the target window 115 and weight coefficients. R and C respectively represent characteristic values (e.g., such as luminance and chrominance information) of the matching window 125 and the target window 115, and the SAD is calculated as an equation below:
                    SAD        =                              ∑                          i              =              0                        n                    ⁢                                    ∑                              j                =                0                            k                        ⁢                                                                          R                  ij                                -                                  C                  ij                                                                                                      equation        ⁢                                  ⁢        1            
Certain positions in the matching window 125 are sometimes the focus of image matching, and so a weight may be added into the SAD calculation to reinforce the significance of pixels at these positions. The SAD calculated with a weight is referred to as a weighted SAD (WSAD). As shown in FIG. 2, a weight coefficient group 210 includes a weight coefficient W corresponding to each of the pixels in the matching window 125 and the target window 115. The WSAD is calculated as an equation below:
                    WSAD        =                              ∑                          i              =              0                        n                    ⁢                                    ∑                              j                =                0                            k                        ⁢                          (                                                                                                            R                      ij                                        -                                          C                      ij                                                                                        ×                                  W                  ij                                            )                                                          equation        ⁢                                  ⁢                  (          2          )                    
Compared the SAD calculated without a weight (equation (1)), the WSAD involves an additional multiplication operation, which poses an extra load for an image processing circuit implemented by either hardware or software.
For the sake of simplicity, an example where n and k are both equal to 2 is given below to illustrate the window matching calculation based on a WSAD. FIG. 3 shows a schematic diagram of a conventional image matching calculation procedure based on 3×3 matching windows. As shown, a search window 323 has a size of 5×5, and is centered at a corresponding point 327. The corresponding point 327 corresponds to the center 117 of the target window 115 of the target image 110. In the search window 323, nine matching windows having a size of 3×3 are formed. Relative positions of the matching windows 325 and the corresponding point 327 are as shown by nine matching windows 325-00 to 325-22 below the reference image 120. Below the target image 110, weight coefficient groups 310-00 to 310-22 respectively corresponding to the matching windows 325 are depicted. All of the coefficient sets together form a weight coefficient set. Therefore, for a window matching procedure for a search window in a size of 5×5 and a matching window in a size of 3×3, nine rounds of operations based on equation (2) need to be performed to obtain the WSAD values of the nine matching windows 325 to further identify the matching window 325 having the smallest WSAD value.
In the above description, the corresponding point 327 corresponds to the center 117 of the target window 115 of the target image 110. However, in some more complicated algorithms, regarding only the center 117 of the target window 115 for identifying the corresponding points cannot satisfy all kinds of scenarios, and so more sophisticated window matching operations are developed. FIG. 4 shows a diagram of a corresponding relationship of a plurality of search windows generated according to a plurality of corresponding points in a reference image and a target image in the prior art. In this example, the matching windows and the target window are in a same size of 3×3. Respective corresponding points of nine pixels included in a target window 482 in a target image 480 can all be identified in a reference image 460. Thus, in FIG. 4, nine sub-diagrams respectively represent corresponding relationships of nine search windows, a corresponding point, and reference points 484 in the target window 482. Taking the uppermost sub-diagrams for example, the reference point 484 is located at the upper-left corner of the target window 482, a corresponding point 417 can be identified in the reference image 460, and a search window 413 in a size of 5×5 can be determined according to the corresponding point 417. The search window 413 may further determine nine matching windows 415, each of which including the corresponding point 417. Nine relative positions below the reference image 120 in FIG. 3 show a corresponding relationship of the matching window 415 and the corresponding point 417. Other variations of the reference point 484 and the target widow 482 are as shown by the remaining sub-diagrams, and associated description shall be omitted herein. A search window range 410 in the diagram represents a range in which the search window 413 moves about the 9 variations. In this example, the search window range 410 has a length of 7 pixels and a width of also 7 pixels.
According to the above method for calculating the WSAD, each of the matching windows corresponds to one weight coefficient group, and nine different matching windows can be determined based on the nine variations of the search window in FIG. 4. For the window matching procedure in FIG. 4, when calculating the WSAD, there are a total of 9×9=81 weight coefficient groups that need to be considered. FIG. 5 shows a schematic diagram of pixels in a search window range of a reference image and corresponding pixels in a target image. FIG. 6 shows a circuit diagram of a conventional WSAD calculation unit. In FIG. 5, the left half shows the pixels included in the search window range 410 of the reference image 460, and the right half shows the corresponding pixels in the target image 480 to be used for a WSAD operation with the pixels in the search window range 410. The WSADs of all of the matching windows of a search window 510 are first calculated. The search window 510 corresponds to a target window 510C. Characteristic values of nine pixels (R00˜R22) of the upper-left matching window (x=0˜2, y=0˜2) in the search window 510 and nine pixels (C00˜C22) of the corresponding target block (x=0˜2, y=0˜2) in the target window 510C are inputted into the WSAD calculation unit 60 in FIG. 6. The WSAD calculation unit 60 includes nine absolute difference calculation units 610, each of which calculates the absolute difference of the characteristic values of one set of pixels and outputs a value |Rij−Cij|, where i=0˜2 and j=0˜2. A multiplication unit 620 identifies a corresponding weight coefficient group from the weight coefficient set, and multiplies the absolute difference generated in the previous stage by the identified weight coefficient group to obtain a weighted absolute difference. An addition unit 630 then adds up all the nine weighted absolute differences to generate the WSAD of the matching window.
Next, the middle-left matching window (x=0˜2, y=1˜3) (corresponding to the middle-left target block in the target window 510C, and so forth), the lower-left matching window (x=0˜2, y=2˜4), the three middle matching windows (x=1˜3, y=0˜4), and the three right matching windows (x=2˜4, y=0˜4) of the search window 510 are sequentially calculated, until the WSADs of all the nine matching windows of the search window 510 are obtained. For the search window 520 and the target window 520C, and the search window 530 and the target window 530C, the same method is used to calculate the WSADs of the respective nine matching windows. In FIG. 5, there are also respectively three search windows in the middle (x=0˜6, y=1˜5) and at the bottom (x=0˜6, y=2˜6) of the search range 410. Thus, the search window range 410 includes a total of 9×9=81 matching windows. To simultaneously obtain 81 WSADs, 81 of the WSAD calculation unit 60 shown in FIG. 6 are needed. Further, each of the WSAD calculation units 60 includes nine absolute difference calculation units 610, leading to a considerable amount of logic gates required. In the above description, a 3×3 matching window is given as an example for explaining a circuit required. That is to say, even more hardware resources are needed for a larger matching window, resulting in drawbacks of increased costs and excessively large circuit areas.